Лабораторная работа №4

Математические основы защиты информации и информационной безопасности

Леонтьева К. А., НПМмд-02-23

Российский университет дружбы народов

Москва, Россия

14 октября 2023

Цель лабораторной работы

  1. Реализовать на языке программирования алгоритмы Евклида для вычисления наибольшего общего делителя

Теоретическое введение

Целое число d ≠ 0 называется наибольшим общим делителем целых чисел a1, a2, ..., ak (обозначается d= НОД (a1,a2,...,ak)), если выполняются следующие условия:

  • каждое из чисел a1, a2, ..., ak делится на d,

  • если d1 ≠ 0 - другой общий делитель чисел a1, a2, ..., ak, то d делится на d1.

Для вычисления наибольшего общего делителя двух целых чисел применяется способ повторного деления с остатком, называемый алгоритмом Евклида.

Теоретическое введение

Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0 < b ≤ a):

  1. если оба числа a и b четные, то НОД(a,b) = 2* НОД$(\frac {a}{2}, \frac{b}{2})$

  2. если число a - нечетное, число b -четное, то НОД(a,b)= НОД$(a, \frac{b}{2})$

  3. если оба числа a и b нечетные, a > b, то НОД(a,b)= НОД(ab,b)

  4. если a = b, то НОД(a,b) = a

Ход выполнения лабораторной работы

  • Реализуем алгоритм Евклида
Рис.1: Алгоритм Евклида

Ход выполнения лабораторной работы

  • Реализуем бинарный алгоритм Евклида
Рис.2: Бинарный алгоритм Евклида

Ход выполнения лабораторной работы

  • Реализуем расширенный алгоритм Евклида
Рис.3: Расширенный алгоритм Евклида

Ход выполнения лабораторной работы

  • Реализуем расширенный бинарный алгоритм Евклида
Рис.4: Расширенный бинарный алгоритм Евклида

Вывод

  • В ходе выполнения данной лабораторной работы были реализованы алгоритмы Евклида для вычисления наибольшего общего делителя